1. Field of the Invention
The present invention relates to a technique for searching a route to a destination, extending via a place selected by a user, in a navigation apparatus mounted in a vehicle, etc.
2. Description of Related Art
With respect to a navigation apparatus mounted in a vehicle, a technique of searching a route extending from a departure place to a destination on the basis of road map data and suggesting the route thus searched as a recommendable route to a user has been put into practice.
Further, there has also been put into practice such a technique of accepting user's selection of one or plural stopovers and a destination from a plurality of stopover candidates and destination candidates which are prepared in advance in a route searching operation, and then searching a route extending from a departure place to the destination by way of each of the selected stopovers. Here, "stopover" means a place through which a route from a departure place to a destination necessarily passes. The stopover candidates and the destination candidates are various frequently prepared abilities which may generally be used by users, for example, sights, parking places, service areas, gasoline service stations, etc.
Since there are cases where stopovers and destinations thus selected are not located on roads, the following method has been hitherto adopted in order to determine a route extending from a departure place through stopovers to a destination. That is, a route extending from the departure place to an intersection/branching point of a road nearest to the facilities selected as a first stopover is searched, and then a route from the intersection/branching point to an intersection/branching point of a road nearest to the facilities selected as a next stopover is searched. This processing is repeated until a route to the final stopover is searched. Finally, a route extending from the final stopover to an intersection/branching point nearest to the destination is searched.
The operation of searching a route between places on a road is performed by a technique referred to as the Dijkstra's algorithm. According to this method, a route having the minimum cost is searched from available routes between places. The total distance of the route is frequently used as the "cost" of the route.